In microprocessors, out-of-order scheduling is an important mechanism to improve the performance of the microprocessors. Typically, hardware logic in the microprocessors finds independent operations within a processing window that can be done in parallel. The out-of-order operations are executed in parallel to increase the overall rate of executing instructions.
FIG. 1 illustrates a block diagram 100 of a prior art out-of-order scheduler 105. The prior art out-of-order scheduler 105 has a multiplexer (Mux) 110, a flip-flop 115, a compare logic 120, a ready logic 130, and a pick logic 140. The flip-flop 115 shows that the compare logic 120, ready logic 130, and the pick logic 140 are required to be completed within a single cycle. Once an operation has been selected by the pick logic 140, the operation is sent to the opcode/data module 150 via the multiplexer 110.
The opcode/data module 150 sends in parallel, the operation to the arithmetic logic unit (ALU) control decode module 160 for decoding of the operation and the data of the operation to the ALU control decode module 160 via the bypass module 170 and the flip-flop 175. When the decoding is completed, the operation is sent to the ALU module 180 for execution.
FIG. 2 illustrates a sequence 210 of prior art operations. Instruction 1 210 is a load instruction that loads the contents from the memory of the address found in the register eax into the register esi. The instructions 2-5 220, 230, 240 and 250 are addition instructions.
FIG. 3A illustrates a timing sequence 300 of a prior art in-order scheduler that schedules the sequence 210 of prior art operations sequentially. The instruction 1 210 is scheduled (SCH) in cycle 1 and it requires 3 cycles to complete. In cycle 2, the Address Generation Unit (AGU) stage creates the address that is needed to lookup a data cache based on the input source of instruction 1 210. The data cache is assumed to require cycles 3 and 4 to be accessed. The instruction 2 220 is scheduled in cycle 4 and goes through the execution stage 1 (EX1) in cycle 5. Similarly, instructions 3-5 230, 240, and 250 are executed sequentially after instruction 2 220.
FIG. 3B illustrates a timing sequence 350 of a prior art out-of-order scheduler 105. The instruction 3 230 is independent of the other instructions and is scheduled in cycle 1 in parallel with instruction 1 210. Instructions 4-5 240, and 250 are executed after the instruction 3 230. Each scheduling involves executing the compare, ready and pick logic. The prior art in-order scheduler and the prior art out-of-order scheduler 105 complete the scheduling of the sequence 210 of prior art operations in eight and five cycles respectively.
Although the prior art out-of-order scheduler 105 is faster than the prior art in-order scheduler, it requires the execution of the compare, ready and pick logic within a single cycle. This process is often timing critical and it limits the size of the scheduler and/or the frequency of the logic.